Introduction to Machine Learning

Unit 10: Boosting and Stacking

Introduction

Welcome to Unit 10, where we explore Boosting techniques, with a focus on the AdaBoost algorithm.

Key Concept:

Boosting is an ensemble learning technique that combines multiple weak learners (models that are slightly better than random guessing) to create a strong learner. Unlike bagging (e.g., Random Forest) where models train independently in parallel, boosting builds models sequentially, with each new model focusing on the training examples that previous models struggled with.

This lecture covers:

Theory

How Boosting Works

Boosting operates through a sequential training process in which later models place greater emphasis on examples that earlier models handled poorly:

  1. Sequential Training: Models are built one after another
  2. Adaptive Weighting: After each model:
    • ✗ Misclassified instances → Higher weights (more important)
    • ✓ Correctly classified instances → Lower weights (less important)
  3. Learning from Errors: Model \(M_{i+1}\) focuses on training examples that Model \(M_i\) struggled with
  4. Weighted Voting: Final predictions combine weak learners using model weights derived from their weighted training errors.

Adaptive Boosting (AdaBoost)

Developed by Freund and Schapire in the 1990s, AdaBoost is one of the most influential boosting algorithms. Freund and Schapire received the Gödel Prize in 2003 for their work on the algorithm.

AdaBoost's Dual Weight System:

  1. Sample Weights (\(w_i\)): Control which training instances each model focuses on
    • Misclassified instances → weights increase
    • Correctly classified instances → weights decrease
    • Each new predictor "pays more attention" to previously misclassified examples
  2. Model Weights (\(\alpha_j\)): Control how much each predictor contributes to final prediction
    • Based on the model's weighted training error (\(\varepsilon\))
    • Lower error → Higher \(\alpha\) → Stronger vote in ensemble
    • Formula: \(\alpha = \frac{1}{2} \ln \left(\frac{1 - \varepsilon}{\varepsilon}\right)\)

The Sequential Process

The AdaBoost algorithm follows this iterative process:

\[ \begin{align*} &1.\ \text{Train } M_1 \rightarrow \text{Calculate error } \varepsilon_1 \rightarrow \text{Determine } \alpha_1 \rightarrow \text{Update sample weights} \\ &2.\ \text{Train } M_2 \rightarrow \text{Calculate error } \varepsilon_2 \rightarrow \text{Determine } \alpha_2 \rightarrow \text{Update sample weights} \\ &3.\ \text{Train } M_3 \rightarrow \text{Calculate error } \varepsilon_3 \rightarrow \text{Determine } \alpha_3 \rightarrow \text{Update sample weights} \\ &\ldots \\ &\text{Final Prediction: } H(x) = \text{sign}\left(\sum \alpha_j \cdot h_j(x)\right) \end{align*} \]

Where:

Building the Weak Learners

In boosting, the ensemble often consists of very simple base classifiers, commonly referred to as weak learners:

  • Typical weak learner: Decision tree stump (decision tree with depth = 1)
  • Key concept: Focus on training examples that are hard to classify
  • Unlike Random Forests (which use bootstrap samples), each weak learner in AdaBoost is trained on the entire dataset
  • After each weak learner is trained, the sample weights are updated so that incorrectly classified examples receive greater weight

Model Weight Formula

The model-weight formula gives better-performing weak learners greater influence in the final ensemble:

\[ \alpha = \frac{1}{2} \ln \left(\frac{1 - \varepsilon}{\varepsilon}\right) \]

Properties:

Pseudocode for AdaBoost

1. Set the weight vector, w, to uniform weights, where ∑ᵢ wᵢ = 1. 2. For j in m boosting rounds, do the following:
a. Train a weighted weak learner: Cⱼ = train(X, y, w).
b. Predict class labels: ȳ = predict(Cⱼ, X).
c. Compute the weighted error rate: ε = w · (ȳ ≠ y).
d. Compute the coefficient: αⱼ = 0.5 log((1 - ε)/ε).
e. Update the weights: w ⇐ w × exp(-αⱼ × ȳ × y).
f. Normalize the weights to sum to 1: w ⇐ w / ∑ᵢ wᵢ.
3. Compute the final prediction: ȳ = (∑ⱼ₌₁ᵐ(αⱼ × predict(Cⱼ, X)) > 0).

Weight Update Mechanism

The AdaBoost sample-weight update is given by:

\[ w_{\text{new}} = w_{\text{old}} \times \exp(-\alpha_t \times y_i \times h_t(x_i)) \]

Where:

Learning Rate (Shrinkage)

The learning rate, \(\eta \in (0, 1]\), also called the shrinkage parameter (with a default value of 1), controls the magnitude of the weight updates:

\[ w_{t+1} = w_t(i) \times \exp(-\eta \cdot \alpha_t \cdot y_i \cdot h_t(x_i)) \]

Where: \(h_t(x_i)\) = prediction of weak learner t on sample i

Bagging vs. Boosting

Aspect Bagging (Random Forest) Boosting (AdaBoost)
Training Parallel (independent models) Sequential (each model depends on previous)
Data Sampling Bootstrap samples (with replacement) Full dataset (with adaptive weights)
Focus Reduces variance Reduces bias
Combining Predictions Simple averaging / majority voting Weighted voting (based on accuracy)
Overfitting Risk Low (due to independence) Medium-High (can overfit to noise)
Typical Accuracy Good Often better (but can be worse if overfit)

Theory

Gradient Boosting

Proposed by Friedman in 2001, Gradient Boosting is another popular ensemble method that combines multiple decision trees:

Key Difference from AdaBoost:

Unlike AdaBoost, which updates sample weights, Gradient Boosting:

  • Does not adjust the weights of training examples
  • For regression with squared-error loss, each new predictor can be trained on the residual errors of the current ensemble; more generally, Gradient Boosting fits each new learner to the negative gradient of the loss function
  • Focuses on minimizing a loss function (e.g., mean squared error for regression, log loss for classification)

Note: We will study Gradient Boosting in more detail when we cover regression analysis.

Boosting Variants Comparison

Algorithm Year Key Innovation Best For
AdaBoost 1997 Sample weighting Binary classification
Gradient Boosting 2001 Residual fitting Regression & classification
XGBoost 2014 Speed & regularization Large datasets, competitions
LightGBM 2017 Memory efficiency Very large datasets
CatBoost 2017 Categorical handling Mixed data types

Common Thread: All these algorithms build ensembles sequentially and learn from errors, but they differ in how they implement this learning process.

Detailed Algorithm Descriptions

AdaBoost
Gradient Boosting
XGBoost
LightGBM
CatBoost

AdaBoost

Assigns weights to data points, and each subsequent weak learner focuses on the samples that the previous ones misclassified. Effective for binary classification problems.

  • Strengths: Simple, effective for binary classification, theoretically well-founded
  • Weaknesses: Sensitive to noisy data and outliers, can overfit with many iterations
  • Typical Use: Binary classification, text classification, face detection

Gradient Boosting

Works by iteratively training a weak learner to minimize the gradient of the loss function with respect to the predictions of the previous learners. The final model is a weighted ensemble of the weak learners.

  • Strengths: Flexible, works for both regression and classification, can handle various loss functions
  • Weaknesses: Can be slow to train, prone to overfitting without proper regularization
  • Typical Use: Regression tasks, classification, ranking problems

XGBoost (Extreme Gradient Boosting)

A highly efficient and scalable implementation of Gradient Boosting with numerous optimizations:

  • Tree pruning: Stops growing trees when they no longer improve performance
  • Parallelization: Builds trees using multiple CPU cores
  • Regularization: Includes L1 and L2 regularization to prevent overfitting
  • Handling missing values: Built-in support for missing data
  • Cross-validation: Built-in cross-validation at each boosting iteration
  • Early stopping: Stops training when performance stops improving

Why it's popular: It is widely used because of its speed, scalability, and strong predictive performance.

LightGBM (Light Gradient Boosting Machine)

Developed by Microsoft, this algorithm focuses on memory efficiency and fast training:

  • Histogram-based learning: Discretizes/bins numeric columns and splits only on bin boundaries
  • Leaf-wise growth: Grows trees leaf-by-leaf (best-first) instead of level-by-level
  • Memory optimization: Uses less memory than traditional boosting methods
  • Faster training: Particularly efficient for large datasets
  • GPU support: Can utilize GPU acceleration

Best for: Very large datasets where memory efficiency is critical.

CatBoost (Categorical Boosting)

Developed by Yandex, this algorithm focuses on handling categorical features efficiently:

  • Automatic encoding: Automatically encodes categorical variables without extensive preprocessing
  • Ordered boosting: Implements a novel approach to handle categorical features
  • Reduced prediction shift: Reduces a source of bias that can arise when target statistics for categorical features are computed in a way that uses information from the same observations being predicted
  • Built-in categorical support: No need for one-hot encoding or other preprocessing
  • Robust to overfitting: Includes built-in regularization

Best for: Datasets with many categorical features or mixed data types.

Performance Comparison (Typical)

Metric AdaBoost XGBoost LightGBM CatBoost
Speed Moderate Fast Very Fast Fast
Memory Usage Low Moderate Low Moderate
Accuracy Good Excellent Excellent Excellent
Overfitting Risk Low-Medium Low Medium Very Low
Ease of Use Easy Moderate Moderate Easy
Categorical Support Poor Manual Manual Automatic

Which to Choose?

  • Small datasets, binary classification: AdaBoost
  • Medium datasets, competitions: XGBoost
  • Very large datasets, memory constraints: LightGBM
  • Datasets with categorical features: CatBoost

In practice, the best choice depends on dataset size, feature types, available resources, and the specific modeling objective.

Stacking: The Next Level of Ensembles

So far, we have seen two common ways of combining models:

Existing Ensemble Methods:

  • Bagging (Random Forest): Average predictions (hard or soft voting)
  • Boosting (AdaBoost): Weighted voting based on model accuracy

The Stacking Idea: Instead of using a fixed rule such as averaging or voting, stacking learns how to combine the predictions of the base learners.

Stacking (Stacked Generalization) uses a two-level model structure in which a meta-learner learns how to combine the predictions of the base learners.

Stacking Architecture

Stacking uses a two-level hierarchy:

Stacking Model Architecture A stacking ensemble architecture showing multiple level one base models producing predictions that are combined by a level two meta-learner into a final prediction. STACKING MODEL Multi-level ensemble learning architecture LEVEL 1 LEVEL 2 Base Model 1 (Level 1) Base Model 2 (Level 1) Base Model k (Level 1) Predictions Model 1 output Predictions Model 2 output Predictions Model k output Meta-Learner (Level 2) Combines base predictions Final Prediction How the architecture works 1 Level 1 · Base Learners • Train multiple diverse models on original data • Heterogeneous algorithms may include: Logistic Regression · Decision Tree · SVM · KNN • Homogeneous algorithms can vary by hyperparameters Each learner contributes an independent prediction signal. 2 Level 2 · Meta-Learner • Learns to optimally combine base learner predictions • Input features: predictions from base learners • Output: final prediction • Typically a simple model, such as: Logistic Regression or Linear Regression

The Power of Diversity: Different base learners make different types of errors → Meta-learner learns which to trust for different types of inputs.

Stacking Process

A basic stacking procedure follows these steps:

  1. Step 1: Split training data: Original Training Set → Train Set + Validation Set
  2. Step 2: Train base learners on Train Set (e.g., Model 1 = Random Forest, Model 2 = Logistic Regression, Model 3 = SVM)
  3. Step 3: Generate meta-features by applying base learners to Validation Set and collect their predictions as new features
  4. Step 4: Train meta-learner
    • Input: Base learner predictions (from Step 3)
    • Output: Original labels from Validation Set
  5. Prediction Phase: New data → Base Learners → Predictions → Meta-Learner → Final Prediction

Critical Note: Preventing Data Leakage

To prevent data leakage, the predictions used as meta-features should be generated for observations that were not used to train the corresponding base learner. This is commonly achieved through k-fold cross-validation.

Why it matters: If the meta-learner is trained on predictions from base learners that were fitted on the same observations, those predictions can be overly optimistic and cause the meta-learner to learn patterns that do not generalize to new data.

Python Implementation Example

# Define multiple models
models = {
    # Distance/probability-based - NEED scaling
    'KNN': Pipeline([
        ('scalar', MinMaxScaler()),
        ('knn', KNeighborsClassifier(n_neighbors=19))
    ]),
    'Naive Bayes': Pipeline([
        ('scalar', MinMaxScaler()),
        ('nb', GaussianNB())
    ]),
    # Tree-based models - NO scaling needed
    'Decision Tree': DecisionTreeClassifier(max_depth=10, random_state=42),
    'Random Forest': RandomForestClassifier(random_state=42),
    'Extra Trees': ExtraTreesClassifier(random_state=42),
    'AdaBoost': AdaBoostClassifier(random_state=42),
    'XGBoost': xgb.XGBClassifier(random_state=42, eval_metric='logloss'),
    'LightGBM': lgb.LGBMClassifier(random_state=42, verbose=-1),
    'CatBoostClassifier': CatBoostClassifier(random_state=42, verbose=0)
}

Key Observations from Performance Comparisons:

  • Gradient boosting variants (XGBoost, LightGBM, CatBoost) consistently outperform other models across all datasets
  • Tree-based ensembles generally perform better than distance-based models (KNN) and probabilistic models (Naive Bayes)
  • Performance differences are more pronounced on imbalanced datasets (like Credit Card)
  • CatBoost often provides the best performance, especially with categorical features
  • AdaBoost still performs well but is typically slightly behind the modern variants

These comparisons illustrate that ensemble performance depends on both the algorithm and the characteristics of the dataset.

Interactive Examples

Example: Step-by-Step AdaBoost

Consider the following step-by-step example with 10 data points:

Initial Setup:

  1. Add a weight of 1 to every point
  2. Fit a weak learner
  3. Results: Correct: 7, Incorrect: 3
  4. Rescale misclassified points by 7/3
Round 1
Round 2
Round 3

Round 1:

Initial weights: All samples have weight = 1

Weak Learner 1:

  • Accuracy: 7 / 10
  • Error: \(\varepsilon_1 = 3/10 = 0.3\)
  • Score: \(\alpha_1 = \ln(7/3) = 0.847\) (using simplified formula)

Weight Update:

  • Correctly classified (7 samples): \(w_{new} = w_{old} \times \exp(-\alpha_1 \times 1) = 0.064\)
  • Incorrectly classified (3 samples): \(w_{new} = w_{old} \times \exp(-\alpha_1 \times (-1)) = 0.1528\)
  • Normalized: Correct = 0.0714, Incorrect = 0.1667

Round 2:

Rescaled dataset: Misclassified points have higher weights

Weak Learner 2:

  • Sum of correct: 11
  • Sum of incorrect: 3
  • Accuracy: 11 / 14
  • Score: \(\alpha_2 = \ln(11/3) = 1.299\)

Round 3:

Rescaled dataset: Further emphasis on hard examples

Weak Learner 3:

  • Sum of correct: 19
  • Sum of incorrect: 3
  • Accuracy: 19 / 22
  • Score: \(\alpha_3 = \ln(19/3) = 1.846\)

Numerical Solutions

Weight Calculation Example

Consider the following dataset and calculate the corresponding weight updates:

Index x y Initial Weights Prediction (ŷ) Correct? Updated Weights
11.010.11✓ Yes0.072
22.010.11✓ Yes0.072
33.010.11✓ Yes0.072
44.0-10.1-1✓ Yes0.072
55.0-10.1-1✓ Yes0.072
66.0-10.1-1✓ Yes0.072
77.010.1-1✗ No0.167
88.010.1-1✗ No0.167
99.010.1-1✗ No0.167
1010.0-10.1-1✓ Yes0.072

Step-by-Step Calculation:

Given: \(\alpha_1 = 0.847\) (from Round 1)

For correctly classified samples (7 samples):

  • \(y_i \times h_t(x_i) = +1\)
  • \(w_{new} = w_{old} \times \exp(-\alpha_1 \times 1) = 0.1 \times \exp(-0.847) = 0.064\)

For incorrectly classified samples (3 samples):

  • \(y_i \times h_t(x_i) = -1\)
  • \(w_{new} = w_{old} \times \exp(-\alpha_1 \times (-1)) = 0.1 \times \exp(0.847) = 0.1528\)

Normalization:

  • Sum of new weights = (0.064 × 7) + (0.1528 × 3) = 0.448 + 0.4584 = 0.9064
  • Correct Samples: 0.064 / 0.9064 ≈ 0.0706
  • Incorrect Samples: 0.1528 / 0.9064 ≈ 0.1686

Combining Weak Learners

After the weak learners have been trained, the final classification is obtained by weighted voting:

\[ H(x) = \text{sign}\left(\sum_{j=1}^m \alpha_j \cdot h_j(x)\right) \]

Example Calculation:

Ensemble of weak learners forming a strong learner Three weak learners with weighted coefficients feed into a strong learner formula. Weak learner 1 α₁ = 0.847 Weak learner 2 α₂ = 1.299 Weak learner 3 α₃ = 1.846 Strong Learner H(x) = sign(0.847×h₁(x) + 1.299×h₂(x) + 1.846×h₃(x))

Try It Yourself

Problem 1: AdaBoost Weight Calculation

Suppose you have a dataset with 8 samples. After training the first weak learner:

  • 5 samples are correctly classified
  • 3 samples are misclassified
  • Initial weights are uniform: \(w_i = 1/8\) for all samples

Tasks:

  1. Calculate the weighted error rate \(\varepsilon_1\)
  2. Calculate the model weight \(\alpha_1\) using \(\alpha = \frac{1}{2} \ln\left(\frac{1-\varepsilon}{\varepsilon}\right)\)
  3. Calculate the new weights for correctly and incorrectly classified samples
  4. Normalize the weights so they sum to 1

Solution:

  1. Weighted error rate: \(\varepsilon_1 = \frac{\text{sum of weights of misclassified}}{\text{sum of all weights}} = \frac{3 \times 1/8}{8 \times 1/8} = 3/8 = 0.375\)
  2. Model weight: \(\alpha_1 = \frac{1}{2} \ln\left(\frac{1-0.375}{0.375}\right) = \frac{1}{2} \ln(1.\overline{6}) \approx \frac{1}{2} \times 0.5108 \approx 0.2554\)
  3. New weights:
    • Correct: \(w_{new} = \frac{1}{8} \times \exp(-0.2554 \times 1) \approx 0.0915\)
    • Incorrect: \(w_{new} = \frac{1}{8} \times \exp(-0.2554 \times (-1)) \approx 0.1326\)
  4. Normalization:
    • Sum = (0.0915 × 5) + (0.1326 × 3) = 0.4575 + 0.3978 = 0.8553
    • Correct: 0.0915 / 0.8553 ≈ 0.1070
    • Incorrect: 0.1326 / 0.8553 ≈ 0.1550
Problem 2: Final Prediction

Given three weak learners with the following predictions for a test sample:

Weak Learner\(\alpha_j\)\(h_j(x)\)
10.5+1
20.8-1
31.2+1

Task: Calculate the final prediction \(H(x)\) using the AdaBoost formula.

Solution:

Using \(H(x) = \text{sign}\left(\sum \alpha_j \cdot h_j(x)\right)\):

= sign(0.5×1 + 0.8×(-1) + 1.2×1)

= sign(0.5 - 0.8 + 1.2)

= sign(0.9)

= +1

Final prediction: +1 (Positive class)

Problem 3: Understanding Weight Updates

Explain why the following weight update formula \(w_{new} = w_{old} \times \exp(-\alpha \times y_i \times h_t(x_i))\) increases weights for misclassified samples and decreases weights for correctly classified samples.

Solution:

The weight update formula works as follows:

  • For correctly classified samples: \(y_i \times h_t(x_i) = +1\)
    • \(\exp(-\alpha \times 1) = \exp(-\alpha) < 1\) (since \(\alpha > 0\))
    • Therefore, \(w_{new} = w_{old} \times (\text{something} < 1)\) → weight decreases
  • For misclassified samples: \(y_i \times h_t(x_i) = -1\)
    • \(\exp(-\alpha \times (-1)) = \exp(\alpha) > 1\) (since \(\alpha > 0\))
    • Therefore, \(w_{new} = w_{old} \times (\text{something} > 1)\) → weight increases

Intuition: The formula automatically increases the importance of hard-to-classify samples and reduces the importance of easy samples, forcing subsequent weak learners to focus on the difficult cases.

Problem 4: Stacking Implementation

Suppose you want to create a stacking ensemble with the following base learners:

  • Logistic Regression
  • Random Forest
  • SVM

Tasks:

  1. Describe the training process for the meta-learner
  2. What type of model would you choose for the meta-learner and why?
  3. How would you prevent data leakage during training?

Solution:

  1. Training process:
    1. Split the original training data into two parts: training set and validation set
    2. Train each base learner (Logistic Regression, Random Forest, SVM) on the training set
    3. Apply each base learner to the validation set to generate predictions
    4. Use these predictions as features (meta-features) to train the meta-learner
    5. The target for the meta-learner is the original labels from the validation set
  2. Meta-learner choice: Logistic Regression (for classification) or Linear Regression (for regression). Reason: The meta-learner should be simple to avoid overfitting on the meta-features. Complex models might overfit the specific patterns in the base learners' predictions.
  3. Preventing data leakage: Use k-fold cross-validation. Split the training data into k folds. For each fold:
    1. Train base learners on k-1 folds
    2. Generate predictions for the held-out fold
    3. Use these predictions as meta-features for the meta-learner
    This ensures that the meta-learner never sees predictions from base learners that were trained on the same data it's being tested on.
Problem 5: Boosting Variant Selection

Suppose you have a dataset with the following characteristics:

  • Very large (10 million samples)
  • Contains both numerical and categorical features
  • Limited memory resources
  • Need for fast training

Task: Which boosting variant would you choose and why?

Solution:

Recommended: LightGBM

Reasoning:

  • Memory efficiency: LightGBM uses histogram-based learning, which is more memory-efficient than traditional boosting methods. This is crucial for very large datasets.
  • Speed: LightGBM is optimized for speed and can handle large datasets efficiently. It uses leaf-wise growth which can be faster than level-wise growth in some cases.
  • Categorical handling: While LightGBM requires manual encoding of categorical variables, this can be handled during preprocessing. The memory savings and speed benefits outweigh this limitation for large datasets.

Alternative consideration: CatBoost would be a good second choice since it handles categorical features automatically, but it might use more memory than LightGBM for very large datasets.

Interactive Quiz

Use these multiple-choice questions to test your understanding of Boosting and AdaBoost:

Score: 0 / 5

Key Takeaways

  • Sequential Learning: Boosting builds models one after another, with each new model focusing on examples that previous models handled poorly.
  • Adaptive Weighting: Misclassified samples get higher weights, forcing subsequent models to pay more attention to difficult cases.
  • Weighted Voting: Final predictions combine all weak learners with weights proportional to their accuracy.
  • Weak Learners: AdaBoost typically uses decision tree stumps (depth=1) as base classifiers.
  • Model-Weight Formula: The model weight \(\alpha = \frac{1}{2} \ln\left(\frac{1-\varepsilon}{\varepsilon}\right)\) gives lower-error classifiers greater influence.
  • Weight Update: \(w_{new} = w_{old} \times \exp(-\alpha \times y_i \times h_t(x_i))\) automatically increases weights for misclassified samples.
  • Learning Rate: The \(\eta\) parameter controls weight update magnitude, providing regularization against overfitting.
  • Bagging vs Boosting: Bagging trains models in parallel on bootstrap samples, while boosting trains models sequentially on weighted data.

Common Pitfalls

  • Overfitting: Boosting can overfit the training data, especially with too many weak learners. Use early stopping or learning rate (shrinkage) to prevent this.
  • Noisy Data: Boosting is sensitive to noisy data and outliers. The algorithm will try to fit the noise, which can degrade performance.
  • Choosing k: For decision tree stumps, depth is fixed at 1. Don't confuse this with the number of weak learners (which is a hyperparameter to tune).
  • Weight Initialization: Always initialize weights to sum to 1 (typically \(1/n\) for n samples). Don't forget to normalize after each update.
  • Numerical Stability: When \(\varepsilon = 0\) (perfect classifier), the formula for \(\alpha\) becomes undefined (division by zero). In practice, add a small constant to \(\varepsilon\) to avoid this.
  • Interpretation: Boosting models are often less interpretable than single models. The ensemble nature makes it hard to understand individual predictions.
  • Computational Cost: Boosting can be computationally expensive, especially with many weak learners and large datasets.
  • Class Imbalance: While boosting can handle class imbalance to some extent, extreme imbalance might require additional techniques like oversampling.